package vj.linkedlist.sort;

import vj.linkedlist.Node;

public class InsertionSort {

	public static Node insertSort(Node head) {
		Node cur, next, result = null;
		cur = head;
		while(cur != null) {
			// very tricky, save the next node
			next = cur.next;
			result = sortedInsert(result, cur);
			cur = next;
		}
		return result;
	}
	
	private static Node sortedInsert(Node head, Node node) {
		if(head == null || node.data < head.data) {
			// step very critical. The result list has to be terminated by null
			node.next = head;
			return node;
		}
		Node cur = head;
		// locate the node before point of insertion
		while(cur.next != null && cur.next.data < node.data)
			cur = cur.next;
		node.next = cur.next;
		cur.next = node;
		return head;
	}
}
